import java.util.ArrayDeque;

public class ConvertBiNode {
  class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int x) { val = x; }
  }
  public TreeNode convertBiNode(TreeNode root) {
      TreeNode dummy = new TreeNode(-1);
      if(root == null){
        return dummy;
      }
      TreeNode prev = dummy;
      TreeNode curr = root;
      ArrayDeque<TreeNode> stack = new ArrayDeque<>();
      while(curr!=null || !stack.isEmpty()){
        while(curr != null){
          stack.push(curr);
          curr = curr.left;
        }
        if(!stack.isEmpty()) {
          curr = stack.pop();
          prev.right = curr;
          prev = curr;
          curr.left = null;
          curr = curr.right;
        }
      }
      return dummy.right;
  }
  public static void main(String[] args) {
    ConvertBiNode c = new ConvertBiNode();
    TreeNode root = c.new TreeNode(4); // Qualify with the enclosing instance
    root.left = c.new TreeNode(2);
    root.left.left = c.new TreeNode(1);
    root.left.right = c.new TreeNode(3);
    root.left.left.left = c.new TreeNode(0);
    root.right = c.new TreeNode(5);
    root.right.right = c.new TreeNode(6);
    TreeNode res = c.convertBiNode(root);
    while(res != null){
      System.out.println(res.val);
      res = res.right;
    }
  }
}

// 二叉树数据结构TreeNode可用来表示单向链表（其中left置空，right为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。

// 返回转换后的单向链表的头节点。

// 注意：本题相对原题稍作改动

 

// 示例：

// 输入： [4,2,5,1,3,null,6,0]
// 输出： [0,null,1,null,2,null,3,null,4,null,5,null,6]
// 提示：

// 节点数量不会超过 100000。